package dp;

import org.junit.Test;

public class MaximalSquare221 {
    @Test
    public void test() {
        maximalSquare(new char[][]{new char[]{'0', '1'}, new char[]{'0', '1'}});
    }

    // 这不是最优的方法, 官方的方法只用了dp[i][j]表示以[i][j]为右下角的最大正方形边长, 且有
    // dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
    public int maximalSquare(char[][] m) {
        int x = m.length;
        int y = m[0].length;
        int w = Math.min(x, y);
        int maxWidth = 0;
        boolean[][][] dp = new boolean[x][y][w+1];

        for (int k = 1; k <= w; k++) {
            // 注意限制i和j的上界, 不是x和y了, 要减去k
            for (int i = 0; i < x-k+1; i++) {
                for (int j = 0; j < y-k+1; j++) {
                    if (k == 1) {
                        dp[i][j][k] = (m[i][j] == '1');
                    } else {
                        boolean isSquare = dp[i][j][k-1];
                        if (i + 1 < x) {
                            isSquare = isSquare && dp[i+1][j][k-1];
                        }
                        if (j + 1 < y) {
                            isSquare = isSquare && dp[i][j+1][k-1];
                        }
                        if (i + 1 < x && j + 1 < y) {
                            isSquare = isSquare && dp[i+1][j+1][k-1];
                        }
                        dp[i][j][k] = isSquare;
                    }
                    if (dp[i][j][k] && k > maxWidth) {
                        maxWidth = k;
                    }
                }
            }
        }
        System.out.format("x: %d, y: %d, maxWidth: %d", x, y, maxWidth);
        return maxWidth*maxWidth;
    }
}
